課程資訊
課程名稱
資料結構與進階程式設計
Data Structures and Advanced Program Design 
開課學期
110-2 
授課對象
管理學院  資訊管理學系  
授課教師
李根逸 
課號
IM1010 
課程識別碼
705 10600 
班次
 
學分
3.0 
全/半年
半年 
必/選修
必帶 
上課時間
星期二7,8,9(14:20~17:20) 
上課地點
管一102 
備註
本課程中文授課,使用英文教科書。
限本系所學生(含輔系、雙修生)
總人數上限:80人 
 
課程簡介影片
 
核心能力關聯
核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

This is an introductory course on data structures concerning the various ways of organizing data so that the data can be accessed and manipulated efficiently by an application. A central concept is that of an abstract data type, which is a collection of data and a set of operations on the data. The course, therefore, focuses on the fundamental concepts, techniques, and tools for the design and implementation of abstract data types, following the teaching of object-oriented design and programming for computer problem-solving. We use the programming language C++ in this course. 

課程目標
請見 NTU COOL 
課程要求
非資管系同學,請優先考慮加簽資訊工程系的「資料結構與演算法」 (CSIE1212)。有其他原因需要加簽者,請在第一堂課下課 (2022/02/15 下午 17:20) 前填寫加簽意願表單 (https://forms.gle/WN62yy3oLpYWYfu27),以便屆時被加入 NTU COOL 成為旁聽生以撰寫第一次作業。我們將在第二堂課上課 (2022/02/22 下午 14:20) 前依照下列的順位發送授權碼加簽:

(1) 修習且通過資管系「程式設計」(IM1003) 課程
(2) 第一次作業的成績較高者
(3) 第一次作業的繳交時間較早者

PS1:本門課所有作業都需要在該週週日深夜前繳交,遲交即為零分
PS2:本門課重於實作,務必已有撰寫 C++ 經驗的程式基礎。
PS3:本門課為資管必修課,作業負擔較重。每週都需要在課堂外投入不少的時間寫作業,且嚴禁抄襲 
預期每週課後學習時數
 
Office Hours
另約時間 
指定閱讀
 
參考書目
Data Abstraction and Problem Solving with C++ : Walls and Mirrors by Carrano and Henry, sixth edition, Pearson, 2012
C++ How to Program: Horizon Edition, 8th Edition, Harvey M. Deitel and Paul Deitel, Pearson, 2013
Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, 2009 
評量方式
(僅供參考)
 
No.
項目
百分比
說明
1. 
程式作業與報告 
60% 
預計共 11 次作業,約每週一次,遲交即為零分。每人的所有成績裡面最低的一次不計,取其他前十高的成績 
2. 
期中與期末考 
24% 
 
3. 
期末專題與競賽 
10% 
 
4. 
課堂參與 
6% 
 
 
課程進度
週次
日期
單元主題
第1週
02/15  第 1 章:資料結構與進階程式設計課程簡介 (Introduction to the Course)
第 2 章:C++ 程式語言基礎 (Basics of C++) 
第2週
02/22  第 3 章:C++ 的抽象機器 (Abstract Machine in C++)
第 4 章 : 抽象資料型態 (Abstract Data Type) 
第3週
03/01  第 5 章:陣列 (Array) 與字串 (String)
 
第4週
03/08  第 6 章:資源管理 (Resource Management)
第 7 章:程式測試、錯誤處理與例外 (Testing, Error Handling and Exception) 
第5週
03/15  第 8 章:物件導向程式設計基礎 (Basics of OOP)
第 9 章:演算法的效率 (Algorithm Efficiency)
第 10 章:多重集、集合與字典 (Multiset, Set, and Dictionary)  
第6週
03/22  第 11 章:排序 (Sorting)
第 12 章:遞迴與分治 (Recursion and Divide-and-Conquer)
第 13 章:二元搜尋法 (Binary Search)  
第7週
03/29  第 14 章:雜湊表 (Hash table)
第 15 章:單向鏈結串列 (Singly Linked List)
第 16 章:迭代器 (Iterator) 與 泛型演算法 (Generic Algorithm) 簡介 
第8週
04/05  春假不上課 (Spring Break) 
第9週
04/12  期中考 (Midterm Exam) 
第10週
04/19  第 17 章:堆疊 (Stack)
第 18 章:佇列 (Queue) 與雙向鏈結串列 (Doubly Linked List)
第 19 章:回溯法 (Back-tracking) 與深度/廣度優先搜尋 (DFS/BFS) 簡介 
第11週
04/26  第 20 章:動態規劃 (Dynamic Programming) 簡介
第 21 章:樹 (Tree)
第 22 章:序列化 (Serialization) 簡介  
第12週
05/03  第 23 章:堆積 (Heap) 與優先佇列 (Priority Queue)
第 24 章:二元搜尋樹 (Binary Search Tree)
第 26 章:2-3-4 Tree 
第13週
05/10  第 27 章:AVL Tree
第 28 章:紅黑樹 (Red-Black Tree)
第 29 章:B-tree 
第14週
05/17  第 30 章:圖 (Graph) 與最短路徑問題 (Shortest Path Problem) 簡介
第 31 章:進階資料結構與程式設計議題漫談 
第15週
05/24  期末考 (Final Exam) 
第16週
05/31  期末專題 (Final Project) Demo 與競賽